# cronmon - Cron e-mail filtering and management
# Copyright (c) 2010 Crown copyright
# 
# This file is part of cronmon.
# 
# cronmon is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# cronmon is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with cronmon.  If not, see <http://www.gnu.org/licenses/>.

"""A parser for a simple boolean logic grammar to query tags"""

import re
import operator


class Node(object):
    """Abstract syntax tree node"""

    def tags(self):
        """All tags mentioned in this node"""
        raise NotImplementedError("Subclasses must implement this method")


class TagNode(Node):
    def __init__(self, name):
        self.name = name

    def match(self, tags):
        return self.name in tags

    def pprint(self, indent=''):
        return indent + '<%s>' % self.name

    def tags(self):
        return set([self.name])


class ConjunctionNode(Node):
    def __init__(self, children):
        self.children = children

    def match(self, tags):
        for c in self.children:
            if not c.match(tags):
                return False
        return True

    def tags(self):
        return reduce(operator.or_, [c.tags() for c in self.children])

    def pprint(self, indent=''):
        return indent + '(\n' + ' &\n' . join([c.pprint(indent + '  ') for c in self.children]) + '\n' + indent + ')'


class DisjunctionNode(Node):
    def __init__(self, children):
        self.children = children

    def match(self, tags):
        for c in self.children:
            if c.match(tags):
                return True
        return False

    def tags(self):
        return reduce(operator.or_, [c.tags() for c in self.children])

    def pprint(self, indent=''):
        return indent + '(\n' + ' |\n' . join([c.pprint(indent + '  ') for c in self.children]) + '\n' +  indent + ')'


class NegationNode(Node):
    def __init__(self, child):
        self.child = child

    def match(self, tags):
        return not self.child.match(tags)

    def tags(self):
        return self.child.tags()

    def pprint(self, indent=''):
        return indent + '!( ' + self.child.pprint() + ' )'


class RuleSyntaxError(SyntaxError):
    """There was an error parsing a rule"""


TOK_WHITESPACE = 0
TOK_SYMBOL = 1
TOK_TAG = 2

toktypes = [
    (TOK_WHITESPACE, re.compile(r'\s+')),
    (TOK_SYMBOL, re.compile(r'\||&|!|\(|\)')),
    (TOK_TAG, re.compile(r'[\w-]+')),
]


def tokens(rule):
    while rule:
        for tok, regex in toktypes:
            mo = regex.match(rule)
            if mo:
                rule = rule[mo.end():]
                yield tok, mo.group()
                break
        else:
            raise RuleSyntaxError("Could not extract token")
        

class Production(object):
    def __init__(self, pattern, callback):
        assert bool(pattern)
        self.pattern = pattern
        self.callback = callback

    def match(self, stack):
        if len(stack) < len(self.pattern):
            return False
        sslice = stack[-len(self.pattern):]
        for i, p in enumerate(self.pattern):
            if isinstance(p, type) and issubclass(p, Node):
                if not isinstance(sslice[i], p):
                    return False
            elif sslice[i] != p:
                    return False
        return True

    def apply(self, stack):
        """Apply the production to the stack in place"""
        sslice = stack[-len(self.pattern):]
        del stack[-len(self.pattern):]
        stack.append(self.callback(sslice))
        

productions = [
    Production(['!', Node], lambda stack: NegationNode(stack[1])), 
    Production([DisjunctionNode, '|', Node], lambda stack: DisjunctionNode(stack[0].children + [stack[2]])), 
    Production([ConjunctionNode, '&', Node], lambda stack: ConjunctionNode(stack[0].children + [stack[2]])), 
    Production([Node, '|', Node], lambda stack: DisjunctionNode([stack[0], stack[2]])), 
    Production([Node, '&', Node], lambda stack: ConjunctionNode([stack[0], stack[2]])), 
    Production(['(', Node, ')'], lambda stack: stack[1]), 
]

class RuleParser(object):
    def parse(self, rule):
        self.stack = []
        toks = tokens(rule)
        while True:
            if not self.reduce():
                if not self.shift(toks):
                    break

        if len(self.stack) > 1:
            raise RuleSyntaxError("Could not completely reduce expression")

        try:
            if not isinstance(self.stack[0], Node):
                raise RuleSyntaxError("Invalid expression")

            return self.stack.pop()
        except IndexError:
            raise RuleSyntaxError("Empty Rule")

    def shift(self, toks):
        try:
            sym, tok = toks.next()
        except StopIteration:
            return False
        else:
            if sym == TOK_WHITESPACE:
                return self.shift(toks)
            if sym == TOK_TAG:
                self.stack.append(TagNode(tok))
            elif sym == TOK_SYMBOL:
                self.stack.append(tok) 
            else:
                raise ValueError("Unknown token type")
            return True

    def reduce(self):
        for p in productions:
            if p.match(self.stack):
                p.apply(self.stack)
                return True
        return False


if __name__ == '__main__':
    parser = RuleParser()
    print parser.parse('!logwatch&error').pprint()
    print
    print parser.parse('(error|warning|alert) & !logrotate').pprint()
